|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (advisor) ; Dvořák, Zdeněk (referee)
We study sufficient degree conditions that force a host graph to contain a given class of trees. This setting involves some well-known problems from the area of extremal graph theory. The most famous one is the Erdős-Sós conjecture that asserts that every graph with average degree greater than k − 1 contains any tree on k + 1 vertices. Our two main results are the following. We prove an approximate version of the Erdős-Sós conjecture for dense graphs and trees with sublinear max- imum degree. We also study a natural refinement of the Loebl-Komlós-Sós conjecture and prove it is approximately true for dense graphs. Both results are based on the so-called regularity method. The second mentioned result is a joint work with T. Klimošová and D. Piguet. 1
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (advisor) ; Keevash, Peter (referee) ; Krivelevich, Michael (referee)
of doctoral thesis Structural graph theory Jan Hladký In the thesis we make progress on the Loebl-Komlós-Sós Conjecture which is a classic problem in the field of Extremal Graph Theory. We prove the following weaker version of the Conjecture: For every α > 0 there exists a number k0 such that for every k > k0 we have that every n-vertex graph G with at least (1 2 +α)n vertices of degrees at least (1+α)k contains each tree T of order k as a subgraph. The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we develop a decomposition technique that applies also to sparse graphs: each graph can be decomposed into vertices of huge degrees, regular pairs (in the sense of the Regularity Lemma), and two other components each exhibiting certain expander-like properties. The results were achieved in a joint work with János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein and Endre Szemerédi. 1
|
|
|
Vlastnosti síťových centralit
Pokorná, Aneta ; Hartman, David (advisor) ; Balko, Martin (referee)
The need to understand the structure of complex networks increases as both their complexity and the dependency of human society on them grows. Network centralities help to recognize the key elements of these networks. Betweenness centrality is a network centrality measure based on shortest paths. More precisely, the contribution of a pair of vertices u, v to a vertex w ̸= u, v is the fraction of the shortest uv-paths which lead through w. Betweenness centrality is then given by the sum of contributions of all pairs of vertices u, v ̸= w to w. In this work, we have summarized known results regarding both exact values and bounds on betweenness. Additionally, we have improved an existing bound and obtained more exact formulation for r-regular graphs. We have made two major contributions about betweenness uniform graphs, whose vertices have uniform betweenness value. The first is that all betweenness uniform graphs of order n with maximal degree n − k have diameter at most k, by which we have solved a conjecture posed in the literature. The second major result is that betweenness uniform graphs nonisomorphic to a cycle that are either vertex- or edge-transitive are 3-connected, by which we have partially solved another conjecture. 1
|
|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (advisor) ; Dvořák, Zdeněk (referee)
We study sufficient degree conditions that force a host graph to contain a given class of trees. This setting involves some well-known problems from the area of extremal graph theory. The most famous one is the Erdős-Sós conjecture that asserts that every graph with average degree greater than k − 1 contains any tree on k + 1 vertices. Our two main results are the following. We prove an approximate version of the Erdős-Sós conjecture for dense graphs and trees with sublinear max- imum degree. We also study a natural refinement of the Loebl-Komlós-Sós conjecture and prove it is approximately true for dense graphs. Both results are based on the so-called regularity method. The second mentioned result is a joint work with T. Klimošová and D. Piguet. 1
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (advisor) ; Keevash, Peter (referee) ; Krivelevich, Michael (referee)
of doctoral thesis Structural graph theory Jan Hladký In the thesis we make progress on the Loebl-Komlós-Sós Conjecture which is a classic problem in the field of Extremal Graph Theory. We prove the following weaker version of the Conjecture: For every α > 0 there exists a number k0 such that for every k > k0 we have that every n-vertex graph G with at least (1 2 +α)n vertices of degrees at least (1+α)k contains each tree T of order k as a subgraph. The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we develop a decomposition technique that applies also to sparse graphs: each graph can be decomposed into vertices of huge degrees, regular pairs (in the sense of the Regularity Lemma), and two other components each exhibiting certain expander-like properties. The results were achieved in a joint work with János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein and Endre Szemerédi. 1
|
guest ::
